#include <bits/stdc++.h>

using namespace std;

// 翻转对数量
// 测试链接 : https://leetcode.cn/problems/reverse-pairs/

class Solution 
{
private:
    static const int MAXN = 50010;
    int help[MAXN];

    int merge(vector<int>& nums, int l, int m, int r)
    {
        // 统计部分
        int ans = 0;
        for(int i = l, j = m + 1; i <= m; ++i)
        {
            while(j <= r && (long)nums[i] > (long)2 * nums[j]) ++j;
            ans += j - m - 1;
        }

        // 征程的 merge 过程
        int i = l, a = l, b = m + 1;
        while(a <= m && b <= r)
        {
            help[i++] = nums[a] <= nums[b] ? nums[a++] : nums[b++];
        }
        while(a <= m) help[i++] = nums[a++];
        while(b <= r) help[i++] = nums[b++];
        for(i = l; i <= r; ++i) nums[i] = help[i];

        return ans;
    }
    
	// 统计 l...r 范围上，翻转对的数量，同时 l...r 范围统计完后变有序
	// 时间复杂度 O(n * logn)
    int counts(vector<int>& nums, int l, int r)
    {
        if(l >= r) return 0;
        int m = l + ((r - l) >> 1);
        return counts(nums, l, m) + counts(nums, m + 1, r) + merge(nums, l, m, r);
    }

public:
    int reversePairs(vector<int>& nums) 
    {   
        return counts(nums, 0, nums.size() - 1);
    }
};